The background art references used in the present description are summarized and commented on in a table at the end of the detailed description section. Each of the references cited in this table is hereby incorporated by reference in its entirely. Whenever in the present specification reference is made to the background art (in brackets), it is to be understood that the corresponding document is incorporated thereby by reference.
Many difficulties can arise in applying evolutionary algorithms to solve complex real-world optimization problems. One of the main concerns is that evolutionary algorithms usually need a large number of fitness evaluations to obtain a good solution. Unfortunately, fitness evaluations are often time-consuming. Taking aerodynamic design optimization as an example, one evaluation of a given design based on the 3-Dimensional Computational Fluid Dynamics (CFD) Simulation can take hours even on a high-performance computer.
To alleviate the fact that evolutionary computation is often time consuming, computationally efficient models can be set-up to approximate the fitness function. Such models are often known as approximate models, meta-models or surrogates. For an overview of this topic, see Y. Jin and B. Sendhoff, Fitness approximation in evolutionary computation—A survey, Proceedings of the Genetic and Evolutionary Computation Conference, pages 1105-1112, 2002, which is incorporated by reference herein in its entirety. It would be ideal if an approximate model can fully replace the original fitness function, however, research has shown that it is in general advisable to combine the approximate model with the original fitness function to ensure the evolutionary algorithm to converge correctly. To this end, past solutions require re-evaluation of some individuals using the original fitness function, also termed as evolution control in Y. Jin, M. Olhofer, and B. Sendhoff, On evolutionary optimization with approximate fitness functions, Proceedings of the Genetic and Evolutionary Computation Conference, pages 786-792, Morgan Kaufmann, 2000, which is incorporated by reference herein in its entirety.
Generation-based or individual-based evolution control can be implemented. In the generation-based approach (see A. Ratle Accelerating the convergence of evolutionary algorithms by fitness landscape approximation, A. Eiben, Th. Bäck, M. Schoenauer and H.-P. Schwefel, editors, Parallel Problem Solving from Nature, volume V, pages 87-96, 1998; M. A. El-Beltagy, P. B. Nair, and A. J. Keane, Metamodeling techniques for evolutionary optimization of computationally expensive problems: promises and limitations, in Proceedings of Genetic and Evolutionary Conference, pages 196-203, Orlando, 1999. Morgan Kaufmann; Y. Jin, M. Olhofer, and B. Sendhoff, On evolutionary optimization with approximate fitness functions, in Proceedings of the Genetic and Evolutionary Computation Conference, pages 786-792, Morgan Kaufmann, 2000; Y. Jin, M. Olhofer, and B. Sendhoff, A framework for evolutionary optimization with approximate fitness functions, IEEE Transactions on Evolutionary Computation, 6(5):481-494, 2002, which are all incorporated by reference herein in their entirety) some generations are evaluated using the approximate model and the rest using the original fitness function. In individual-based evolution control, part of the individuals of each generation are evaluated using the approximation model and the rest using the original fitness function. See Y. Jin, M. Olhofer, and B. Sendhoff, On evolutionary optimization with approximate fitness functions, in Proceedings of the Genetic and Evolutionary Computation Conference, pages 786-792, Morgan Kaufmann, 2000; M. Emmerich, A. Giotis, M. Ozdenir, T. Bäck, and K. Giannakoglou, Metamodel assisted evolution strategies, In Parallel Problem Solving from Nature, number 2439 in Lecture Notes in Computer Science, pages 371-380, Springer, 2002; H. Ulmer, F. Streicher, and A. Zell, Model-assisted steady-state evolution strategies, in Proceedings of Genetic and Evolutionary Computation Conference, LNCS 2723, pages 610-621, 2003; J. Branke and C. Schmidt, Fast convergence by means of fitness estimation. Soft Computing, 2003, which are all incorporated by reference herein in their entirety. Generally speaking, the generation-based approach is more suitable when the individuals are evaluated in parallel, where the duration of the optimization process depends to a large degree on the number of generations needed. By contrast, the individual-based approach is better suited when the number of evaluations is limited, for example, when an experiment needs to be done for a fitness evaluation.
On the other hand, individual-based evolution control provides more flexibility in choosing which individuals need to be re-evaluated. In Y. Jin, M. Olhofer, and B. Sendhoff, On evolutionary optimization with approximate fitness functions, Proceedings of the Genetic and Evolutionary Computation Conference, pages 786-792, Morgan Kaufmann, 2000, which is incorporated by reference herein in its entirety, it is suggested to choose the best individuals according to the approximate model rather than choosing the individuals randomly. In M. Emmerich, A. Giotis, M. Ozdenir, T. Bäck, and K. Giannakoglou, Metamodel assisted evolution strategies, Parallel Problem Solving from Nature, number 2439 in Lecture Notes in Computer Science, pages 371-380, Springer, 2002, which is incorporated by reference herein in its entirety, not only the estimated function value but also the estimation error is taken into account. The basic idea is that individuals having a larger estimation error are more likely to be chosen for re-evaluation. Other uncertainty measures have also been proposed in J. Branke and C. Schmidt, Fast convergence by means of fitness estimation, Soft Computing, 2003, which is incorporated by reference herein in its entirety.
In H.-S. Kim and S.-B. Cho, An efficient genetic algorithms with less fitness evaluation by clustering, Proceedings of IEEE Congress on Evolutionary Computation, pages 887-894, IEEE, 2001, which is incorporated by reference herein in its entirety, the population of a genetic algorithm (GA) is grouped into a number of clusters and only one representative individual of each cluster is evaluated using the fitness function. Other individuals in the same cluster are estimated according to their Euclidean distance to the representative individuals. Obviously, this kind of estimation is very rough and the local feature of the fitness landscape is completely ignored.